package org.datastructure.firstday.sort;

import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;

public class RadixSort {
    public static void main(String[] args) {
//        int[] arr = new int[]{53, 3, 542, 748, 14, 214};
//
        int[] arr = new int[8000000];
        for (int i = 0; i < 8000000; i++) {
            arr[i] = (int) (Math.random() * 80000000);
        }

        Date t1 = new Date();
        SimpleDateFormat df = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
        System.out.println(df.format(t1));
        radixSort(arr);
        Date t2 = new Date();
        System.out.println(df.format(t2));

    }

    public static void radixSort(int... arr) {
        int[] bucketElementCounts = new int[10];
        // TODO: 2021/7/8  step 1 将数据放到木桶中去

        int stemp = 0;
        int[][] buckets = new int[10][arr.length];
     /*   for (int i = 0; i < arr.length; i++) {
            int digitOfBucket = arr[i] % 10;
            buckets[digitOfBucket][bucketCounts[digitOfBucket]++] = arr[i];
        }

        // TODO: 2021/7/8 将数据从木桶中取出并放到原数组
        int temp = 0;
        for (int i = 0; i < bucketCounts.length; i++) {
            if (bucketCounts[i] > 0) {
                for (int j = 0; j < bucketCounts[i]; j++) {
                    arr[temp++] = buckets[i][j];
                }
            }
        }

        System.out.println(Arrays.toString(arr));
        bucketCounts = new int[10];
        //TODO: 分解step 2
        for (int i = 0; i < arr.length; i++) {
            int digitOfBucket = arr[i] / 10 % 10;
            buckets[digitOfBucket][bucketCounts[digitOfBucket]++] = arr[i];
        }
        temp = 0;
        for (int i = 0; i < bucketCounts.length; i++) {
            if (bucketCounts[i] != 0) {
                for (int j = 0; j < bucketCounts[i]; j++) {
                    arr[stemp++] = buckets[i][j];
                }
            }
        }
        System.out.println(Arrays.toString(arr));
*/

        // TODO: step 1 先将数组根据不同位上的数依次放入木桶中去
        // TODO: 根据最大数的位数决定排序次数,要算出每次从个位数/十位/百位。。。进行排序，必须要先除以1/10/100
        int length = (Arrays.stream(arr).max().getAsInt() + "").length();
        int digitOfBucket = 0;
        int index = 0;
        for (int l = 0, n = 1; l < length; l++, n *= 10) {
            for (int i = 0; i < arr.length; i++) {
                digitOfBucket = arr[i] / n % 10;
                // TODO:  bucketElementCounts[digitOfBucket]=buckets这个二维数组列数
                buckets[digitOfBucket][bucketElementCounts[digitOfBucket]++] = arr[i];
            }
            // TODO: step 2 将桶中的元素按照桶的顺序，和桶中从小到大依次放入原数组
            index = 0;
            for (int k = 0; k < bucketElementCounts.length; k++) {
                if (bucketElementCounts[k] != 0) {
                    for (int j = 0; j < bucketElementCounts[k]; j++) {
                        // TODO: 存的时候bucketElementCounts[digitOfBucket]和buckets的行下标是对应的，
                        //   即bucketElementCounts[digitOfBucket]中存的是buckets行中的元素个数
                        arr[index++] = buckets[k][j];
                    }
                }
                // TODO: 这里要将元素个数清空，否则下次将桶中数据赋值给arr使，致使判断错误和取数据错误
                bucketElementCounts[k] = 0;
            }
        }
    }
}
